//链式
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>

#define TYPE int 

typedef struct Node
{
	TYPE data;
	struct Node* left;
	struct Node* right;
}Node;



//创建结点
Node* creat_node(TYPE data)
{
	Node* node = malloc(sizeof(Node));
	node->data=data;
	node->left=NULL;
	node->right=NULL;
	return node;
}

//添加
bool add_tree(Node* root,TYPE data);
//删除
bool del_tree1(Node* root,TYPE data);
//修改
bool modify_tree(Node* root,TYPE old,TYPE new);
//访问
bool access_tree(Node* root,size_t i,TYPE* p);

//前序
void prev_show(Node* root);
//中序
void in_show(Node* root);
//后序
void post_show(Node* root);
//层序(广度优先的遍历)
void level_show(Node* root);

//高度
size_t high_tree(Node* root);
//密度
size_t density_tree(Node* root);





int main()
{
	Node* tree = creat_node(50);
	for(int i=0;i<10;i++)
	{
		TYPE data=rand()%100;
		add_tree(tree,data);
		printf("%d\n",data);
	}
	printf("------------------------------\n前序：");
	prev_show(tree);
	printf("\n中序：");
	in_show(tree);
	printf("\n后序：");
	post_show(tree);
	printf("\n=============================\n");
	TYPE data = 0;
	access_tree(tree,4,&data);
	printf("=====%d====\n",data);
	printf("密度:%u\n",density_tree(tree));
	printf("高度:%u\n",high_tree(tree));
	
//	del_tree1(tree,77);
	in_show(tree);
}

void _add_tree(Node* root,Node* node)
{
	if(NULL == root)  return;	
	
	if(root->data >node->data)
	{
		if(NULL == root->left)
		{
			root->left = node;
			return ;
		}
		_add_tree(root->left,node);
		return;
	}
	else
	{
		if(NULL == root->right)
		{
			root ->right =node;
			return;
		}
		 _add_tree(root->right,node);
		return; 
	}
	
}



//添加
bool add_tree(Node* root,TYPE data)
{
	if(NULL == root)  return false;	
	
	if(root->data >data)
	{
		if(NULL == root->left)
		{
			root->left = creat_node(data);
			return true;
		}
		return add_tree(root->left,data);
	}
	else
	{
		if(NULL == root->right)
		{
			root ->right =creat_node(data);
			return true;
		}
		return add_tree(root->right,data);
	}

}
//删除,如果根结点允许被删除，需要使用二级指针
//1.0 根结点不允许被删除
bool del_tree1(Node* root,TYPE data)
{
	if(NULL ==root) return false;
	if(data<root->data)
	{
		if(NULL!=root->left && data == root->left->data); 
		{
			Node* node =root->left;
			root ->left=root->left->left;
			_add_tree(root->left,node->right);
			free(node);
			return true;
		}
		return	del_tree1(root->left,data);
	}
	else
	{
		if(NULL!=root->right && data ==root->right->data); 
		{
			Node* node =root->right;
			root ->left=root->right->left;
			_add_tree(root->right,node->right);
			free(node);
			return true;

		}	
		return	del_tree1(root->right,data);
	}

	

}

//2.0
bool del_tree2(Node* root,TYPE data)
{
	
}
//修改
bool modify_tree(Node* root,TYPE old,TYPE new)
{
	
}


//访问
void _access_tree(Node* root,size_t i,TYPE* p,size_t* indexp)
{
	if( NULL==root) return ;
	_access_tree(root->left,i,p,indexp);
	if(i==*indexp)
	{
		*p = root->data;
		*indexp += 1;
		return ;
	}
	*indexp+=1;
	_access_tree(root->right,i,p,indexp);
}
bool access_tree(Node* root,size_t i,TYPE* p)
{
	if(i>=density_tree(root))	return false;
	size_t index = 0;
	_access_tree(root,i,p,&index);
	return true;
}

//前序
void prev_show(Node* root)
{
	if(NULL == root) return;
	printf("%d ",root->data);
	prev_show(root->left);
	prev_show(root->right);
}
//中序
void in_show(Node* root)
{
	if(NULL == root) return;
	in_show(root->left);
	printf("%d ",root->data);
	in_show(root->right);
}
//后序
void post_show(Node* root)
{
	if(NULL == root) return;
	post_show(root->left);
	post_show(root->right);
	printf("%d ",root->data);
}
//层序(广度优先的遍历)
void level_show(Node* root)
{
	
}




//高度
size_t high_tree(Node* root)
{
	if(NULL == root) return 0;
	size_t lh = high_tree(root->left);
	size_t rh = high_tree(root->right);
	return lh>rh?lh+1:rh+1;
}
//密度
size_t density_tree(Node* root)
{
	if(NULL==root) return 0;
	return 1+density_tree(root->left)+density_tree(root->right);
}


